package com.coder.algorithm.offer_2;

import java.util.Locale;

/**
 * n 个骰子的点数
 *
 * @author yuhushuan
 * @date 2020/7/3 10:17
 */
public class _60_1_DicesProbability {
    private final static int MAX_VALUE = 6;

    private static void printProbability_Recursively(int number) {
        if (number < 1) {
            return;
        }
        int max = number * MAX_VALUE;
        int[] probabilities = new int[max - number + 1];
        // 计算次数
        probability_Recursively(number, probabilities);

        // 总计组合数
        int total = (int) Math.pow(MAX_VALUE, number);
        for (int i = number; i <= max; ++i) {
            int count = probabilities[i - number];
            double ratio = count / (double) total;
            System.out.println(String.format(Locale.getDefault(),
                    "数字 %2d 出现 %d 次，概率为 %f", i, count, ratio));
        }

    }

    private static void probability_Recursively(int number, int[] probabilities) {
        // 骰子出现点数情况
        for (int i = 1; i <= MAX_VALUE; ++i) {
            probability_Recursively(number, number, i, probabilities);
        }
    }

    private static void probability_Recursively(int original, int current, int sum,
                                                int[] probabilities) {
        // 一个骰子的情况
        if (current == 1) {
            probabilities[sum - original]++;
        } else {
            for (int i = 1; i <= MAX_VALUE; ++i) {
                probability_Recursively(original, current - 1, sum + i, probabilities);
            }
        }
    }

    private static void printProbability_Iteratively(int number) {
        if (number < 1) {
            return;
        }
        // 用于记录点数和出现的次数，下标为点数和
        int[][] probabilities = new int[2][number * MAX_VALUE + 1];

        int flag = 0;

        // 第一个骰子出现次数
        for (int i = 1; i <= MAX_VALUE; ++i) {
            probabilities[flag][i] = 1;
        }
        // 第 k 个骰子
        for (int k = 2; k <= number; ++k) {
            // 清除记录
            for (int i = 0; i < k; ++i) {
                probabilities[1 - flag][i] = 0;
            }
            // 遍历所有点数和 [k,k * MAX_VALUE]
            for (int i = k; i <= k * MAX_VALUE; ++i) {
                probabilities[1 - flag][i] = 0;
                for (int j = 1; j <= MAX_VALUE && i - j >= 0; ++j) {
                    probabilities[1 - flag][i] += probabilities[flag][i - j];
                }
            }
            flag = 1 - flag;
        }

        // 总计组合数
        int max = MAX_VALUE * number;
        int total = (int) Math.pow(MAX_VALUE, number);
        for (int i = number; i <= max; ++i) {
            int count = probabilities[flag][i];
            double ratio = count / (double) total;
            System.out.println(String.format(Locale.getDefault(),
                    "数字 %2d 出现 %d 次，概率为 %f", i, count, ratio));
        }
    }

    public static void main(String[] args) {
        // 功能测试 1、2、3、4
        print(1);
        print(2);
        print(3);
        print(4);
        // 特殊输入测试
        print(0);
        // 性能测试
        print(11);
    }

    private static void print(int number) {
        System.out.println(String.format(Locale.getDefault(),
                "%d 个骰子出现的点及概率为：", number));
        long time = System.currentTimeMillis();
        System.out.println("基于递归实现：");
        printProbability_Recursively(number);
        System.out.println("耗时：" + (System.currentTimeMillis() - time) + "ms");
        time = System.currentTimeMillis();
        System.out.println("基于迭代实现：");
        printProbability_Iteratively(number);
        System.out.println("耗时：" + (System.currentTimeMillis() - time) + "ms");
        System.out.println();
    }
}
